package com.crazyxmq.tree;
// 二叉查找树
public class BinaryTree<Key extends Comparable<Key>,Value> {

    private Node root;

    //记录树中元素的个数
    private int N;

    private class Node{
        //存储键
        public Key key;
        // 存储值
        public Value value;

        public Node left;

        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // 获取树中元素的个数
    public int size(){
        return N;
    }

    // 向树中添加元素
    public void put(Key key,Value value){
        root = put(root,key,value);
    }

    private Node put(Node x ,Key key,Value value){
        // 如果x子树为空
        if(x == null){
            N++;
            return new Node(key,value,null,null);
        }

        //如果x子树不为空
        int compare = key.compareTo(x.key);

        if(compare > 0){ //比x结点key大 ，找x的右子树
           x.right =  put(x.right,key,value);
        }else if(compare < 0){ // 比x的结点key小， 找x的左子树
            x.left = put(x.left,key,value);
        }else{ // 值相等，进行替换
            x.value = value;

        }

        return x;
    }

    //查询树中指定key对应的value
    public Value get(Key key){
        return get(root, key);
    }

    public Value get(Node x, Key key){

        // x = null
        if(x == null){
            return null;
        }

        // x!= null
        int compare = key.compareTo(x.key);

        if(compare > 0){ //比x结点key大 ，找x的右子树
          return get(x.right,key);
        }else if(compare < 0){ // 比x的结点key小， 找x的左子树
           return get(x.left,key);
        }else{ // 值相等，进行替换
            return x.value;
        }

    }

    //删除结点，删除某个结点后，与之相邻的三个结点要断开，从被
    //删除的结点的右子树中，找一个最小的值，充当被删除的结点
    //最小的结点与之前被断开的三个结点重新连接
    // 最小的结点断开原有的连接
    public void delete(Key key){
        delete(root,key);
    }

    public Node delete(Node x,Key key){

        // x == null
        if(x == null){
            return null;
        }

        // x!= null
        int compare = key.compareTo(x.key);

        if(compare > 0){ //比x结点key大 ，找x的右子树
           x.right = delete(x.right,key);
        }else if(compare < 0){ // 比x的结点key小， 找x的左子树
           x.left = delete(x.left,key);
        }else{ // 要删除的结点
           if(x.right == null){
               return x.right;
           }

           if(x.left == null){
               return x.left;
           }

           Node minNode = x.right;

           while (minNode.left !=null){
               minNode = minNode.left;
           }
           // 删除右子树中的最小结点
            Node n = x.right;
            while(n.left!=null){
                if(n.left.left == null){
                    n.left = null;
                }else{
                    n = n.left;
                }
            }

            minNode.left = x.left;

            minNode.right = x.right;

            x = minNode;

            N--;
        }


        return x;
    }






}
